package previous.Test_0301;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //下降最小路径和
    public int minFallingPathSum(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int[][] dp=new int[m+1][n+2];
        for (int i = 1; i <= m; i++) {
            dp[i][0]=Integer.MAX_VALUE;
        }
        for (int i = 1; i <= m; i++) {
            dp[i][n+1]=Integer.MAX_VALUE;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i-1][j+1],dp[i-1][j-1]))+matrix[i][j];
            }
        }
        int ret=Integer.MAX_VALUE;
        for (int i = 1; i <=n; i++) {
            ret=Math.min(ret,dp[m][i]);
        }
        return ret;
    }
    //最小路径和
    //dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1]
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m+1][n+1];
        for (int i = 0; i <=n; i++) {
            dp[0][i]+=Integer.MAX_VALUE;;
        }
        for (int i = 0; i <=m; i++) {
            dp[i][0]=Integer.MAX_VALUE;
        }
        dp[0][1]=dp[1][0]=0;
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <=n ; j++) {
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }
    //地下城游戏：求初始最小血包，从下到上，从右向左
    //dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]
    public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length;
        int n=dungeon[0].length;
        int[][] dp=new int[m+1][n+1];
        for (int i = 0; i <=n; i++) {
            dp[m][i]=Integer.MAX_VALUE;
        }
        for (int i = 0; i <=m; i++) {
            dp[i][n]=Integer.MAX_VALUE;
        }
        dp[m-1][n]=dp[m][n-1]=1;
        for (int i = m-1; i >=0 ; i--) {
            for (int j = n-1; j >=0 ; j--) {
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                //血包太大
                dp[i][j]=Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
}
